package q994_orangesRotting;

import java.util.Deque;
import java.util.LinkedList;

/*
腐烂的橘子经过多少时间能够影响全部橘子的问题
此题类似于q542 只需要进行广度遍历即可
 */
public class Solution {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int orangesRotting(int[][] grid) {
        int badOrangeCount = 0, goodOrangeCount = 0;
        Deque<int[]> queue = new LinkedList<>();
        // 首先遍历整个矩阵 统计好的橘子和坏的橘子数量
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    badOrangeCount++;
                    queue.offer(new int[] {i, j});
                }else if (grid[i][j] == 1) {
                    goodOrangeCount++;
                }
            }
        }
        // 如果没有一个好橘子 就直接返回0分钟
        if (goodOrangeCount == 0) {
            return 0;
        }
        // 没有一个坏橘子 就不能影响至全部橘子变坏 返回-1
        if (badOrangeCount == 0){
            return -1;
        }
        // 用来统计时间 但是最后要time - 1 因为本来就坏的橘子不需要一分钟来被影响
        int time = 0;
        // 广度遍历
        while (!queue.isEmpty()) {
            // 这里要注意的是 需要统计循环一次后再加一分钟 所以需要将size提取出来
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int[] origin = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int affect_i = origin[0] + dirs[i][0];
                    int affect_j = origin[1] + dirs[i][1];
                    if (affect_i >= 0 && affect_i < grid.length && affect_j >= 0 && affect_j < grid[0].length && grid[affect_i][affect_j] == 1) {
                        queue.offer(new int[]{affect_i, affect_j});
                        grid[affect_i][affect_j] = 2;
                    }
                }
            }
            // 循环一次再加一分钟
            time++;
        }
        // 结束后需要遍历查看是否还有好橘子 如果有则直接返回-1
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        // 返回时间
        return time - 1;
    }
}
